package leetcode_core.leetcode_1;

import java.util.LinkedList;

public class Codec {
    public class TreeNode {
      int val;
      TreeNode left;
      TreeNode right;
      TreeNode(int x) { val = x; }
    }

    private static final String SEP =",";
    private static final String NULL = "#";
    private StringBuilder sb;


    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        sb = new StringBuilder();
        serialize(root,sb);
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        LinkedList<String> lists = new LinkedList<>();
        //1.将字符串转换为列表
        String[] nodes = data.split(",");//此处得到的nodes列表就是二叉树的前序遍历结果
        //2.如何通过二叉树的前序遍历结果来还原一棵二叉树
        for (String node : nodes) {
            lists.addLast(node);
        }
        TreeNode root = deserialize(lists);
        return root;
    }


    private void serialize(TreeNode root,StringBuilder stringBuilder){
        if(root == null){
            stringBuilder.append(NULL).append(SEP);
            return;
        }
        stringBuilder.append(root.val).append(SEP);
        serialize(root.left,stringBuilder);
        serialize(root.right,stringBuilder);
    }

    private TreeNode deserialize(LinkedList<String> nodes){
        if(nodes.isEmpty()){
            return null;
        }
        String first = nodes.removeFirst();
        if(NULL.equals(first)){
            return null;
        }
        TreeNode root = new TreeNode(Integer.parseInt(first));
        root.left = deserialize(nodes);
        root.right = deserialize(nodes);
        return root;
    }

}
